package com.sfx.算法专题.排序.quicksort;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: sfx
 * Date: 2023-09-04
 * Time: 7:02
 */
public class Code_1_sortColors {

    /**
     * 基本思想就是把数组分为三块
     * [                ]
     * |     |     |
     * left  i     right
     * 我们分别讲一下三个指针的作用
     * i 用来遍历数组中的元素
     * left 代表0的最右侧
     * right代表1的最左侧
     * [0,left] 全是0
     * [left+1,i-1] 全是1
     * [i,right-1] 待扫描的元素
     * [right,n-1] 全是2
     * nums[i] =0 swap(nums[++left],nums[i++]
     * 当nums[i]=0的情况有一个特殊情况就是i=left+1 -->这样就是自己与自己交换
     * nums[i]=1的情况  i++
     * nums[i]=2 swap(nums[i],nums[--right]) i不动,因为--right是带扫描的元素
     */

    static class Solution {
        private void swap(int[] nums, int left, int right) {
            int tmp = nums[left];
            nums[left] = nums[right];
            nums[right] = tmp;
        }

        public void sortColors(int[] nums) {
            int left = -1;
            int right = nums.length;
            int i = 0;
            while (i < right) {
                if (nums[i] == 0) {
                    swap(nums, ++left,i++);
                } else if (nums[i] == 1) {
                    i++;
                } else {
                    swap(nums, i, --right);
                }
            }
        }
    }

    public static void main(String[] args) {

    }
}
